#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2005,C=2000;
int n;
int a[N];
int dp[N][N][2];
int maxn[N][2];
int solve(int i,int x,int y){
    int ans=LLONG_MIN;
    if(a[i]==x) ans=max(ans,dp[i][y][0]);
    if(a[i]==y) ans=max(ans,dp[i][x][1]);
    return ans;
}
void work(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=0;i<=n;i++){
        for(int j=0;j<=C;j++) dp[i][j][0]=dp[i][j][1]=LLONG_MIN; 
    }
    for(int i=0;i<=C;i++) maxn[i][0]=maxn[i][1]=LLONG_MIN;
    maxn[0][0]=0;
    maxn[0][1]=0;
    dp[0][0][0]=dp[0][0][1]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=C;j++){
            dp[i][j][0]=max(solve(i-1,a[i],j)+a[i],maxn[j][1]);
            dp[i][j][1]=max(solve(i-1,j,a[i])+a[i],maxn[j][0]);
        }
        for(int j=0;j<=C;j++){
            maxn[a[i]][0]=max(dp[i][j][0],maxn[a[i]][0]);
            maxn[j][1]=max(dp[i][j][0],maxn[j][1]);
            maxn[a[i]][1]=max(dp[i][j][1],maxn[a[i]][1]);
            maxn[j][0]=max(dp[i][j][1],maxn[j][0]);
        }
    }
    int ans=LLONG_MIN;
    for(int i=0;i<=C;i++) ans=max(ans,max(dp[n][i][0],dp[n][i][1]));
    cout<<ans<<'\n';
}
signed main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    int T;
    cin>>T;
    while(T--) work();
    return 0;
}